ListNode *partition(ListNode *head, int x) {
	ListNode *L1, *L2, *q, *p;
	L1 = new ListNode;
	L1->next = NULL;
	L2 = new ListNode;
	L2->next = NULL;
	q = L2;
	p = L1;
	while (head) {
		if (head->val < x) {
			p->next = head;
			p = head;
		} else {
			q->next = head;
			q = head;
		}
		head = head->next;
	}
	q->next = NULL;
	p->next = L2->next;
	return L1->next;
}